A singly linked list with reverse…
In (not particularly beautiful) C++, both recursive and non-recursive reverse methods:
#include <iostream>
using namespace std;
class ListItem {
public:
ListItem() : next(NULL)
{}
char data[100];
ListItem *next;
void reverse(ListItem *p) {
if(next == NULL) {
next = p;
} else {
next->reverse(this);
next = p;
}
}
};
class LinkedList {
public:
LinkedList() {}
ListItem *start;
ListItem *end;
ListItem *push_back(char *data) {
ListItem *i = new ListItem();
if(end != NULL) { end->next = i; }
else { start = i; }
for(size_t n=0;n<100;n++) {i->data[n] = data[n];}
end = i;
return i;
}
void reverse() {
start->reverse(NULL);
ListItem *temp = end;
end = start;
start = temp;
}
void reverse_nonrec() {
ListItem *last=NULL;
for(ListItem *p=start;p!=NULL;) {
ListItem *next = p->next;
p->next = last;
last = p;
p = next;
}
ListItem *temp = end;
end = start;
start = temp;
}
void dump() {
for(ListItem *p=start;p!=NULL;p=p->next) {
cout << "data: " << p->data << endl;
}
}
~LinkedList() {
ListItem *op = NULL;
for(ListItem *p=start;p!=NULL;p=p->next) {
if(op != NULL) delete op;
op = p;
}
if(op != NULL) delete op;
}
};
int main() {
LinkedList mylist;
char tempdata[100];
for(size_t n=0;n<100;n++) { tempdata[n] = 'A'; }
tempdata[99] = 0;
for(size_t n=0;n<20;n++) {
mylist.push_back(tempdata);
for(size_t n=0;n<99;n++) { tempdata[n]++; }
}
mylist.dump();
mylist.reverse();
cout << "Reversed List" << endl;
mylist.dump();
cout << "Reverse again" << endl;
mylist.reverse_nonrec();
mylist.dump();
}
RSS